#include "GrafoMA.h"

void creaGrafoN(Grafo &G){
    int i,j;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            G[i][j]=false;
}

void agregaArista(Grafo &G, int vert1, int vert2){
    G[vert1][vert2]=true;
    G[vert2][vert1]=true;
}

int gradoVertice(Grafo G, int vertice){
    int j,grado=0;
    for(j=0;j<N;j++)
        if(G[vertice][j])
            grado++;
    if(G[vertice][vertice])     //Tiene lazo, entonces son dos extremps de aristas
        grado++;
    return grado;
}

void desplegaVerticesAdyacentes(Grafo G, int vertice){
    int j;

    for(j=0;j<N;j++)
        if(G[vertice][j])
            printf("%d ", j);
}

bool existeArista(Grafo G, int vert1, int vert2){
    return G[vert1][vert2];
}

bool esGrafoSimple(Grafo G){
    int i=0,j;
    bool simple=true;

    while(i<N&&simple){
        j=i;
        if(G[i][j])
            simple=false;
        i++;
    }
    return simple;
}

bool esGrafoCompleto(Grafo G){
    int i=0,j=0;
    bool completo=true;

    if(esGrafoSimple(G)){
        while(i<N&&completo){
            while(j<N&&completo){
                if((j!=i) && (!G[i][j]))          //Se que no hay lazos, si encuentro cualquier otro false no es completo
                    completo=false;
                j++;
            }
            i++;
        }
    }else
        completo=false;
    return completo;
}

//Grafo no vacio
bool esGrafoRegular(Grafo G){
    int grado,gradoAux,i=1;
    bool regular=true;

    grado=gradoVertice(G,0);

    while(i<N&&regular){
        gradoAux=gradoVertice(G,i);
        if(gradoAux!=grado)
            regular=false;
        i++;
    }
    return regular;
}

bool verticeValido(int V){
    if(V >= N || V < 0 )
        return false;
    else
        return true;
}


/////////////////////////
///////// AUX   /////////
/////////////////////////

bool esGrafoConexo(Grafo G){
Visitado visitado;
int i;
bool conexo=true;

    for(i=0;i<N;i++)
        visitado[i]=false;

    DFSGrafoConexo(G,0,visitado);

    i=0;
    while(i<N&&conexo){
        if(!visitado[i])
            conexo=false;
        i++;
    }
    return conexo;
}

void DFSGrafoConexo(Grafo G, int verticeActual,Visitado visitado){
int j;
visitado[verticeActual] = true;
    for (j=0; j<N; j++){
        if (G[verticeActual][j] == 1){
            if (!visitado[j])
                DFSGrafoConexo(G,j,visitado);
        }
    }
}


/////////////////////////
///////// EJE 1 /////////
/////////////////////////

int cantidadComponentesConexas(Grafo G){
Visitado visitado;
int i,cantComponentes=0, compConexa=0;

    for(i=0;i<N;i++)
        visitado[i]=false;
    i=0;

    while(cantComponentes<N){

        while(visitado[i]&&i<N-1)
            i++;
        compConexa++;
        DFSComponentesConexas(G,i,visitado,cantComponentes);
    }
    return compConexa;
}

void DFSComponentesConexas(Grafo G, int verticeActual,Visitado visitado, int &cantComponentes){
int j;
visitado[verticeActual] = true;
cantComponentes++;

    for (j=0; j<N; j++){
        if (G[verticeActual][j] == 1){
            if (!visitado[j]){
                DFSComponentesConexas(G,j,visitado,cantComponentes);
            }
        }
    }
}


/////////////////////////
///////// EJE 2 /////////
/////////////////////////

//*************Falta hacer una fun que determine si el grafo es conexo*******
//El grafo es conexo

lista caminoMasLargo(Grafo G){
Visitado visitado;
int i,j;
lista listaCamino,listaAux;
crearLista(listaCamino);
crearLista(listaAux);

    for(i=0;i<N;i++){
        for(j=0;j<N;j++)
            visitado[j]=false;
        DFScaminoMasLargo(G,i,visitado,listaCamino,listaAux);
        eliminarLista(listaAux);
        crearLista(listaAux);
    }
    eliminarLista(listaAux);
    return listaCamino;
}

void DFScaminoMasLargo(Grafo G, int verticeActual,Visitado visitado,lista &listaCamino,lista &listaAux){
int j;
insBackLista(listaAux,verticeActual);
visitado[verticeActual] = true;

    for (j=0; j<N; j++){
        if (G[verticeActual][j] == 1){
            if (!visitado[j]){
                DFScaminoMasLargo(G,j,visitado,listaCamino,listaAux);
            }
        }
    }

    if(largoLista(listaAux)>largoLista(listaCamino)){
        eliminarLista(listaCamino);
        listaCamino=copiarLista(listaAux);;
    }
    borrarElementoLista(listaAux,verticeActual);
}


/////////////////////////
///////// EJE 3 /////////
/////////////////////////

int desplegarVertices(Grafo G){
Visitado visitado;
int i;
    for(i=0;i<N;i++)
        visitado[i]=false;

    for(i=0;i<N;i++){
        if(!visitado[i])
            DFSdesplegarVertices(G,i,visitado);
    }

}

void DFSdesplegarVertices(Grafo G, int verticeActual,Visitado visitado){
int j;
visitado[verticeActual] = true;

    printf("%d ",verticeActual);

    for (j=0; j<N; j++){
        if (G[verticeActual][j] == 1){
            if (!visitado[j])
                DFSdesplegarVertices(G,j,visitado);

        }
    }

}
